'''
问题描述：⼀只⻘蛙⼀次可以跳上1级台阶，也可以跳上2级。求该⻘蛙跳上⼀个n级的台阶总共有
多少种跳法。
'''

import time
ARR = [-1 for i in range(10000)]

def f1(n):
    if n<=2:
        return n
    if ARR[n] != -1:
        return ARR[n]
    else:
        ARR[n] = (f1(n-1)+f1(n-2))
        return ARR[n]

def f2(n):
    if n <=2:
        return n
    a1 = 1
    a2 = 2
    for i in range(n-2):
        temp = a1
        a1 = a2
        a2 = temp+a2
    return a2

time1 = time.time()

print(f1(999))

time2 = time.time()
print(time2-time1)

print(f2(999))
time3 = time.time()
print(time3-time2)